package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/reverse-linked-list-ii/">反转链表II [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-22 10:00
 */
public class ReverseLinkedListII_92 {

  public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode newHead = new ListNode(-1); // 创建一个新的头
    newHead.next = head;
    ListNode preNode = newHead;
    for (int i = left - 1; i > 0; i--) { // 将preNode移动到要反转的上一个节点
      preNode = preNode.next;
    }
    ListNode start = preNode.next;
    ListNode end = start;
    for (int i = left; i < right; i++) {
      end = end.next;
    }
    preNode.next = reverse(start, end);
    return newHead.next;
  }

  // 翻转start到end的节点并返回翻转后新的头结点
  public ListNode reverse(ListNode start, ListNode end) {
    end = end.next;
    ListNode pre = null;
    ListNode next;
    ListNode cur = start;
    while (cur != end) {
      next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
    start.next = end; // 将反转后原来的头指向反转后的下一个节点，否则链表断了
    return pre; // 此时pre才是end没有下移之前的位置，即反转后新的头
  }
}
